package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
public class Pra4 {
    //迷宫问题

    public int minPath(int[][] nums, int x1, int y1, int x2, int y2) {
        //nums中，0代表可以走，1代表不能走
        this.visited = new boolean[nums.length][nums[0].length];
        dfs(nums, x1, y1, x2, y2, new LinkedList<>());
        System.out.println("最短路径为:");
        res.forEach(e -> {
            System.out.print(Arrays.toString(e) + " -> ");
        });
        return res == null ? 0 : res.size();
    }

    boolean[][] visited;
    int[] x = {1, -1, 0, 0};
    int[] y = {0, 0, 1, -1};
    List<int[]> res = null;
    public void dfs(int[][] nums, int x1, int y1, int x2, int y2, Deque<int[]> deque) {
        if (x1 == x2 && y1 == y2) {
            if (res == null || deque.size() < res.size()) {
                res = new LinkedList<>(deque);
            }
            return;
        }
        if (!inArea(x1, y1) || !inArea(x2, y2) || visited[x1][y1]) return;
        visited[x1][y1] = true;
        deque.offerLast(new int[]{x1, y1});
        for (int i = 0; i < 4; i++) {
            dfs(nums, x1 + x[i], y1 + y[i], x2, y2, deque);
        }
        deque.removeLast();
    }

    public boolean inArea(int x, int y) {
        return x >= 0 && x < visited.length && y >= 0 && y < visited[0].length;
    }
}
